//
// Created by Tan Ke on 2024/2/19.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

/* 典型的贪心, 从最右向左回溯, 首先将最右的元素置为GOOD, 只要向左遍历
 * 的元素能到达任一GOOD, 这个元素也置为GOOD, 否则就置为BAD
 * 到遍历到最左的元素, 如果最左元素也被置为GOOD, 那就说明能够到达
 * 否则就说明不能到达
 */

enum STATUS {
    GOOD = 0,
    BAD
};

struct Item {
    enum STATUS status;
    int val;
};
bool canJump(int* nums, int numsSize)
{
    struct Item* itemList = (struct Item*)malloc(numsSize * sizeof(struct Item));
    for (int i = 0; i < numsSize; i ++) {
        itemList[i].val = nums[i];
        itemList[i].status = BAD;
    }

    itemList[numsSize-1].status = GOOD;

    for (int i = numsSize - 2; i >= 0; i --) {
        for (int j = i + 1; j < numsSize; j ++) {
            if (itemList[j].status == GOOD && itemList[i].val >= j - i) {
                itemList[i].status = GOOD;
                break;
            }
        }
    }

    return itemList[0].status == GOOD;
}

int main(void)
{
    int nums1[5] = {2, 3, 1, 1, 4};
    printf("%d\n", canJump(nums1, 5));

    int nums2[5] = {3, 2, 1, 0, 4};
    printf("%d\n", canJump(nums2, 5));

    return 0;
}
